public class LinkedNodeTest {
    //定义结点
    static class LinkedNode {
        public int val;
        public LinkedNode next;

        public LinkedNode(int val) {
            this.val = val;
        }
    }
    //刚开始位置
    public LinkedNode head;
    //创建链表
    public LinkedNode createNode() {
        LinkedNode node1 = new LinkedNode(12);
        LinkedNode node2 = new LinkedNode(23);
        LinkedNode node3 = new LinkedNode(34);
        LinkedNode node4 = new LinkedNode(45);
        LinkedNode node5 = new LinkedNode(56);
        //把结点连接起来
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
        return head;
    }

    //遍历链表的每一个节点
    public void traversal(LinkedNode linkedNode) {
        LinkedNode l1 = head;
        while (l1.next != null) {
            System.out.print(l1.val + "\t");
            l1 = l1.next;
        }
    }
    //计算节点的个数
    public int countNode() {
        LinkedNode l1 = head;
        int count = 0;
        while (l1.next != null) {
            count++;
            l1 = l1.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data) {
        LinkedNode node = new LinkedNode(data);
        if (this.head == null) {
            //一个结点也没有的时候
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }
    }

    //尾插法
    public void addLast(int data) {
        LinkedNode node = new LinkedNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            LinkedNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //在任意一个位置插入结点，第一个结点下标为0
    public void addIndex(int index, int data) {
        //要检查index的合法性
        if (index < 0 || index > countNode()) {
            //抛异常
            return;
        }
        if (index == 0) {
            //头插法
            addFirst(data);
            return;
        }
        if (index == countNode()) {
            addLast(data);
            return;
        }
        LinkedNode node = new LinkedNode(data);
        LinkedNode cur = searchPre(index);
        node.next = cur.next;
        cur.next = node;
    }

    //返回前一个节点位置
    private LinkedNode searchPre(int index) {
        LinkedNode cur = this.head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //找到key的前驱
    private LinkedNode findPre(int key) {
        LinkedNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除
    public void remove(int key) {
        if (this.head.val == key) {
            this.head = this.head.next;
        }
        if (this.head == null) {
            return;
        }
        LinkedNode cur = findPre(key);
        if (cur == null) {
            System.out.println("值不存在");
        }else {
            LinkedNode del = cur.next;
            cur.next = del.next;
        }
    }

    //删除更加好的方法（当链表中有重复元素时适合用这个）
    public void remove1(int key) {
        LinkedNode pre = this.head;
        LinkedNode cur = this.head.next;
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        while (cur != null) {
            if (cur.val == key) {
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
    }
    //清空(最好不用this.head操作)
    public void clear() {
        LinkedNode cur = this.head;
        while (cur != null) {
            LinkedNode curNow = cur.next;
            //cur.val = null;//如果值为引用类型的时候要加上这个
            cur.next = null;
        }
        this.head = null;
    }


    //反转链表
    //思想：采用头插法一个一个插
    public LinkedNode reverseList() {
        if (this.head == null) {
            return null;
        }
        if (this.head.next == null) {
            return this.head;
        }
        LinkedNode cur = this.head.next;
        this.head.next = null;
        while (cur != null) {
            LinkedNode node = cur.next;
            cur.next = this.head;
            this.head = cur;
            cur = node;
        }
        return this.head;
    }


    //求中间节点
    public LinkedNode middleNode() {
        //1.先求链表长度
        LinkedNode cur = this.head;
        LinkedNode node = this.head;
        int count = 0;
        int num = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        //2.求长度除2的中间值
        while (num < (count / 2)) {
            num++;
            node = node.next;
        }
        return node;
    }

    //求中间节点(更快速方法)
    //快的走两步，慢的走一步
    public LinkedNode middleNode1() {
        LinkedNode fast = this.head;
        LinkedNode slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    //输出链表倒数第k个节点
    public LinkedNode findKthToTotal(int k) {
        if (k <= 0|| this.head == null) {
            return null;
        }
        LinkedNode fast = this.head;
        LinkedNode slow = this.head;
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
            //要找的节点超出了链表的长度
            if (fast == null) {
                return null;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //链表的回文结构
    public boolean chkPalindrom() {
        if (head == null || head.next == null) {
            return true;
        }
        LinkedNode fast = head;
        LinkedNode slow = head;
        //1.找到中间位置
        while (fast != null && fast.next != null) {//这两个的前后顺序不要弄反了，必须fast！=null在前，否则容易报空的错。
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.翻转
        LinkedNode cur = slow.next;
        while (cur != null) {
           LinkedNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.从前到后，从后到前
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            //偶数情况
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}
